package com.data_structure_algorithm.sort;

import java.util.Arrays;

public class MergerSort {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 6, 3, 2};

        int[] temp = new int[arr.length]; //额外空间

        sort2(arr, 0, arr.length - 1, temp);

        System.out.println(Arrays.toString(arr));

      /*  int[] arrs = new int[10000000];
        for (int i = 0; i < 10000000; i++) {
            arrs[i] = (int) (Math.random() * 80000000);
        }
        String dateStart = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());
        System.out.println(dateStart);
        sort(arrs, 0, arrs.length - 1, new int[arrs.length]);
        String dateEnd = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());

        System.out.println(dateEnd);*/

    }

    private static void sort2(int[] arr, int left, int right, int[] temp) {

        if (left == right) return;
        if (left > right) return;

        if (left < right) {
            //创建中间值
            int mid = (left + right) / 2;

            //左递归分化
            sort2(arr, left, mid, temp);
            //右递归分化
            sort2(arr, mid + 1, right, temp);

            //调用合并
            merge(arr, left, mid, right, temp);
        }


    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {

        //划分左右
        int i = left; //左边索引

        int j = mid + 1;//右边索引

        //临时数组索引
        int tempIndex = 0;

        //保证两边数组都有值
        while (i <= mid && j <= right) {
            //对比
            if (arr[i] <= arr[j]) {
                temp[tempIndex++] = arr[i++];
            } else {
                temp[tempIndex++] = arr[j++];
            }
        }

        //完毕后一端没了
        while (i <= mid) {
            temp[tempIndex++] = arr[i++];
        }

        while (j <= right) {
            temp[tempIndex++] = arr[j++];
        }

        //将临时数组数据拷贝到原数组
        //临时数组index重置
        tempIndex = 0;

        //定位本次数组左边
        int leftIndex = left;

        while (leftIndex <= right) {
            arr[leftIndex++] = temp[tempIndex++];
        }


    }


    public static void sort(int[] arr, int left, int right, int[] tempArr)  {
        //递归条件
        if (left < right) {

            //计算中间值
            int mid = (left + right) / 2;

            //左递归
            sort(arr, left, mid, tempArr);

            //右递归
            sort(arr, mid + 1, right, tempArr);

            //调用合并方法
            mg(arr, left, mid, right, tempArr);

        }
    }

    private static void mg(int[] arr, int left, int mid, int right, int[] tempArr) {

        //左边首元素下标
        int i = left;
        //右边首元素下标
        int j = mid + 1;

        int tempArrIndex = 0;

        while (i <= mid && j <= right) {

            //判断大小
            if (arr[i] <= arr[j]) {
                tempArr[tempArrIndex++] = arr[i++];
            } else {
                tempArr[tempArrIndex++] = arr[j++];
            }
        }
        //退出循环后，一端无数据
        while (i <= mid) {
            //左边还有数据
            tempArr[tempArrIndex++] = arr[i++];
        }

        while (j <= right) {
            //左边还有数据
            tempArr[tempArrIndex++] = arr[j++];
        }

        //------------
        //将临时数据拷贝到原数组
        tempArrIndex = 0; //临时数组复位

        int leftIndex = left;//不断移动    right不动

        while (leftIndex <= right) {//只要还有元素，就复制到原数组
            arr[leftIndex++] = tempArr[tempArrIndex++];

        }


    }


    //分+合并
    public static void mergerSort(int[] arr, int left, int right, int[] tempArr) {

        if (left == right) return;
        if (left > right) return;

        //满足该条件即可继续分
        if (left < right) {
            int mid = (left + right) / 2;
            //左递归分解
            mergerSort(arr, left, mid, tempArr);

            //右
            mergerSort(arr, mid + 1, right, tempArr);

            //合并
            //根据栈特性，最先分离好的，会继续向下执行，回退到这里，我们在这里调用合并方法
            merger(arr, left, mid, right, tempArr);
        }

    }

    //合并
    //arr 原数组
    //left 左边有序序列的初始索引
    //mid 中间索引
    //right 右边有序序列的初始索引
    //tempArr 临时数组
    public static void merger(int[] arr, int left, int mid, int right, int[] tempArr) {

        int i = left;//左侧有序序列的初始索引

        int j = mid + 1; //右边有序序列的初始索引

        int tempIndex = 0;//临时数组的索引初始化,比较过程中，谁小谁进数组

        //将左右两边的有序数据填充到tempArr中
        //结束条件：两边有一边才处理完毕
        while (i <= mid && j <= right) {//左右两边还有数据

            //左边数据小于右边数据，应将左边数据先放入临时数组
            if (arr[i] <= arr[j]) {
                //拷贝当临时数组
                tempArr[tempIndex++] = arr[i++];
            }
            //右边大
            else {
                //拷贝当临时数组
                tempArr[tempIndex++] = arr[j++];
            }
        }


        //一端完毕，另外一端直接拷贝到tempArr的后面
        while (i <= mid) { //左侧有数据
            tempArr[tempIndex++] = arr[i++];
        }

        while (j <= right) { //左侧有数据
            tempArr[tempIndex++] = arr[j++];
        }

        //将tempArr拷贝到arr中
        tempIndex = 0;//临时数组复位

        int leftIndex = left;

        System.out.println("left:" + left + "right:" + right);
        //这里会执行n-1次  如100数据，执行99次
        while (leftIndex <= right) { //本轮还未到最末端
            arr[leftIndex++] = tempArr[tempIndex++];
        }
    }


}
